package com.hooper.solution.day1;

import java.util.HashMap;
import java.util.Map;

/**
 * @author Tim Hooper
 * @version 1.0
 * @time 2023/01/28/18:12
 */
public class Solutions {


    /**
     * 面试题 01.01. 判定字符是否唯一
     * 实现一个算法，确定一个字符串 s 的所有字符是否全都不同。
     * <p>
     * 示例 1：
     * <p>
     * 输入: s = "leetcode"
     * 输出: false
     * 示例 2：
     * <p>
     * 输入: s = "abc"
     * 输出: true
     */
    public boolean isUnique(String str) {
        //思路：
        //使用int数组来记录每个字母出现的次数
        // 若出现的次数超过2则返回false
        int[] chars = new int[26];
        for (int i = 0; i < str.length(); i++) {
            if (++chars[str.charAt(i) - 'a'] > 1) {
                return false;
            }
        }
        return true;
    }

    /**
     * 面试题 01.02. 判定是否互为字符重排
     * 给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
     * 示例 1：
     * 输入: s1 = "abc", s2 = "bca"
     * 输出: true
     * <p>
     * 示例 2：
     * 输入: s1 = "abc", s2 = "bad"
     * 输出: false
     */
    public boolean CheckPermutation(String s1, String s2) {
        //先判断两个字符串长度是否相等
        if (s2.length() != s1.length()) return false;
        //思路：
        //使用int数组记录s1的每个字母的数量
        int[] ans = new int[26];
        for (int i = 0; i < s1.length(); i++) {
            char c = s1.charAt(i);
            ans[c - 'a']++;
        }
        //再次循环将s2所包含的删除，
        // 若字母对应的值<0
        // 则表明s2中含有s1没有的或多于s1的字母
        for (int i = 0; i < s2.length(); i++) {
            if (--ans[s2.charAt(i) - 'a'] < 0) {
                return false;
            }
        }
        return true;
    }

    /**
     * 面试题 01.03. URL化
     * URL化。编写一种方法，将字符串中的空格全部替换为%20。假定该字符串尾部有足够的空间存放新增字符，
     * 并且知道字符串的“真实”长度。（注：用Java实现的话，请使用字符数组实现，以便直接在数组上操作。）
     * 示例 1：
     * 输入："Mr John Smith    ", 13
     * 输出："Mr%20John%20Smith"
     * <p>
     * 示例 2：
     * 输入："               ", 5
     * 输出："%20%20%20%20%20"
     */
    public static String replaceSpaces(String s, int length) {
        StringBuilder builder = new StringBuilder(s.length());
        for (int j = 0; j < length; j++) {
            char c = s.charAt(j);
            builder.append(c == ' ' ? "%20" : c);
        }
        return builder.toString();
    }

    /**
     * 面试题 01.04. 回文排列
     * 给定一个字符串，编写一个函数判定其是否为某个回文串的排列之一。
     * 回文串是指正反两个方向都一样的单词或短语。排列是指字母的重新排列。
     * 回文串不一定是字典当中的单词。
     * 翻译：判断一个字符串在重新排列后是否可以成为一个回文串
     * 示例1：
     * 输入："tactcoa"
     * 输出：true（排列有"tacocat"、"atcocta"，等等
     */
    public boolean canPermutePalindrome(String s) {
        //思路：
        //回文串的特征在于前半部分与后半部分相同
        //也就是说前半部分的各字符数量应与后半部分一致
        //若字符串的长度为奇数，则只有一个字符的个数为奇数
        int len = s.length();
        Map<Character, Integer> map = new HashMap<>(len);
        for (int i = 0; i < len; i++) {
            char c = s.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int count = 0;
        for (Integer value : map.values()) {
            if (value % 2 != 0 && ++count > 1) {
                return false;
            }
        }
        return true;
        //或使用stream，效率更低
        //return map.values().stream().filter(num -> num%2 != 0).count() <= 1;
    }

    /**
     * 面试题 01.05. 一次编辑
     * 字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。 给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。
     * 示例:
     * 输入:
     * first = "pale"
     * second = "ple"
     * 输出: True
     * <p>
     * 示例2:
     * 输入:
     * first = "pales"
     * second = "pal"
     * 输出: False
     */
    public static boolean oneEditAway(String first, String second) {
        int fLen = first.length();
        int sLen = second.length();
        if (Math.abs(fLen - sLen) > 1) return false;
        if (first.equals(second)) return true;
        //分两种情况：
        //第一种 first 的长度与 second 差 1 需要删除一个字符（或在另一个中添加一个字符）
        //第二种 两个长度一样，但只有一个字符不同
        //区分出长短
        String longer = fLen > sLen ? first : second;
        String shorter = longer.equals(first) ? second : first;
        //判断不同的次数
        int diffCount = 0;
        for (int i = 0, j = 0; i < shorter.length(); i++, j++) {
            //对比字符
            if (longer.charAt(j) != shorter.charAt(i)) {
                //若两者长度不同，则短的那个字符串指针向后退一格重新比较
                if (fLen != sLen) {
                    i--;
                }
                //若出现不同的次数超过1则false
                if (++diffCount > 1) {
                    return false;
                }
            }
        }
        return true;
    }
}




















